package com.lin.benchmade.ternary;

public class TernaryTree {
	private Node m_root = null;

	private Node Add(String s, int pos, Node node) {
		char[] charArray = s.toCharArray();
		if (node == null) {
			node = new Node(charArray[pos], false);
		}
		if (charArray[pos] < node.m_char) {
			node.m_left = Add(s, pos, node.m_left);
		} else if (charArray[pos] > node.m_char) {
			node.m_right = Add(s, pos, node.m_right);
		} else {
			if (pos + 1 == charArray.length) {
				node.m_wordEnd = true;
			} else {
				node.m_center = Add(s, pos + 1, node.m_center);
			}
		}
		return node;
	}

	public void Add(String s) throws Exception {
		if (s == null || s == "")
			throw new Exception();
		m_root = Add(s, 0, m_root);
	}

	public boolean Contains(String s) throws Exception {
		char[] charArray = s.toCharArray();
		if (s == null || s == "")
			throw new Exception();
		int pos = 0;
		Node node = m_root;
		while (node != null) {
			int cmp = charArray[pos] - node.m_char;
			if (charArray[pos] < node.m_char) {
				node = node.m_left;
			} else if (charArray[pos] > node.m_char) {
				node = node.m_right;
			} else {
				if (++pos == charArray.length)
					return node.m_wordEnd;
				node = node.m_center;
			}
		}
		return false;
	}
}

class Node {
	char m_char;
	Node m_left, m_center, m_right;
	boolean m_wordEnd;
	public Node(char ch, boolean wordEnd) {
		m_char = ch;
		m_wordEnd = wordEnd;
	}
}